package com.fw.leetcode.stack;

import com.fw.leetcode.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 94. Binary Tree Inorder Traversal
 *
 * Given the root of a binary tree, return the inorder traversal of its nodes' values.
 *
 * Example 1:
 *  Input: root = [1,null,2,3]
 *  Output: [1,3,2]
 *
 * Example 2:
 *  Input: root = []
 *  Output: []
 *
 * Example 3:
 *  Input: root = [1]
 *  Output: [1]
 *
 * Constraints:
 *  The number of nodes in the tree is in the range [0, 100].
 *  -100 <= Node.val <= 100
 *
 * Follow up: Recursive solution is trivial, could you do it iteratively?
 */
public class Num_0094 implements LeetCode {
    private interface Solution extends Tree {
        List<Integer> inorderTraversal(TreeNode root);

        default void assertEquals(Integer[] root, int[] expected) {
            int[] result = inorderTraversal(buildBinaryTree(root)).stream().mapToInt(Integer::intValue).toArray();
            if (!Arrays.equals(result, expected)) {
                inorderTraversal(buildBinaryTree(root));
            }
        }
    }

    private static class MyIteratorSolution implements Solution {

        @Override
        public List<Integer> inorderTraversal(TreeNode root) { // 迭代
            /*
             * 二叉树中序遍历（迭代）
             *       1
             *   -       2
             *         3
             */
            if (root == null) return Collections.emptyList();
            List<Integer> result = new ArrayList<>();
            ArrayDeque<TreeNode> stack = new ArrayDeque<>();
            TreeNode p = root;
            while (p != null || !stack.isEmpty()) {
                // 从任意一个子树根节点开始访问：左 中 右
                while (p != null) { // 找最左叶子
                    stack.push(p);
                    p = p.left;
                }
                p = stack.pop(); // 出栈最左叶子 或 父节点
                result.add(p.val); // 中
                p = p.right; // 右
            }
            return result;
        }
    }

    private static class MyRecursionSolution implements Solution {

        @Override
        public List<Integer> inorderTraversal(TreeNode root) { // 递归
            /*
             * 二叉树中序遍历（递归）
             *       1
             *   -       2
             *         3
             */
            List<Integer> result = new ArrayList<>();
            inorderRecur(root, result);
            return result;
        }

        private void inorderRecur(TreeNode root, List<Integer> result) {
            if (root == null) return;
            inorderRecur(root.left, result);
            result.add(root.val);
            inorderRecur(root.right, result);
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyIteratorSolution();
        solution.assertEquals(new Integer[]{1,null,2,3}, new int[]{1,3,2});
        solution.assertEquals(new Integer[]{}, new int[]{});
        solution.assertEquals(new Integer[]{1}, new int[]{1});
    }
}
